﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LemonKnapsack01
{
    public class Knapsack01
    {
        /// <summary>
        /// 解决0-1背包问题
        /// </summary>
        /// <param name="capacity">背包容量</param>
        /// <param name="weights">物品重量数组</param>
        /// <param name="values">物品价值数组</param>
        /// <returns>最大价值</returns>
        public static int Solve(int capacity, int[] weights, int[] values)
        {
            int n = weights.Length;

            // dp[i, j] 表示前i个物品在容量j下的最大价值
            int[,] dp = new int[n + 1, capacity + 1];

            // 初始化：前0个物品，任何容量下价值都是0
            for (int j = 0; j <= capacity; j++)
            {
                dp[0, j] = 0;
            }

            // 动态规划过程
            for (int i = 1; i <= n; i++)
            {
                for (int j = 0; j <= capacity; j++)
                {
                    // 不选第i个物品
                    dp[i, j] = dp[i - 1, j];

                    // 如果容量足够，考虑选第i个物品
                    if (j >= weights[i - 1])
                    {
                        dp[i, j] = Math.Max(
                            dp[i, j],
                            dp[i - 1, j - weights[i - 1]] + values[i - 1]
                        );
                    }
                }
            }

            return dp[n, capacity];
        }

        /// <summary>
        /// 回溯找出选择的物品
        /// </summary>
        public static void FindSelectedItems(int capacity, int[] weights, int[] values, int[,] dp)
        {
            int n = weights.Length;
            int remainingCapacity = capacity;

            Console.Write("选择的物品: ");
            for (int i = n; i >= 1; i--)
            {
                // 如果当前值不等于上一行的值，说明选择了这个物品
                if (dp[i, remainingCapacity] != dp[i - 1, remainingCapacity])
                {
                    Console.Write($"{i} ");
                    remainingCapacity -= weights[i - 1];
                }
            }
            Console.WriteLine();
        }
    }
}
